package com.lx.algorithm.temp;

import com.advanced.SortList;

import java.util.ArrayList;

/**
 * Description:
 * Copyright:   Copyright (c)2019
 * Company:     zefu
 *
 * @author: 张李鑫
 * @version: 1.0
 * Create at:   2021-11-23 01:16:39
 * <p>
 * Modification History:
 * Date         Author      Version     Description
 * ------------------------------------------------------------------
 * 2021-11-23     张李鑫                     1.0         1.0 Version
 */
public class GetLeastNumbers_Solution {

    public static ArrayList<Integer> GetLeastNumbers_Solution(int [] input, int k) {
        if (input==null||input.length<k){
            return null;
        }
        if (input.length==0){
            return new ArrayList<>();
        }
        sort(input);
        ArrayList<Integer> list = new ArrayList<>();
        for (int i = 0; i < k; i++) {
            list.add(input[i]);
        }
        return list;
    }

    public static void sort(int []input){
        int l=0;
        int r=input.length-1;
        process(input,l,r);
    }

    private static void process(int[] input, int l, int r) {
        if (l==r){
            return;
        }
        int mid=l+((r-l)>>1);
        process(input,l,mid);
        process(input,mid+1,r);
        mergeArr(input,l,mid,r);
    }

    public static void mergeArr(int[] arr, int L, int mid, int R) {
        int p = L;
        int p1 = mid + 1;
        int index = 0;
        int[] merge = new int[R - L + 1];
        while (p <= mid && p1 <= R) {
            merge[index++] = arr[p] < arr[p1] ? arr[p++] : arr[p1++];
        }
        while (p <= mid) {
            merge[index++] = arr[p++];
        }
        while (p1 <= R) {
            merge[index++] = arr[p1++];
        }
        for (int i = 0; i < merge.length; i++) {
            arr[L++] = merge[i];
        }
    }

    public static void main(String[] args) {
        int []arr={4,5,1,6,2,7,3,8};
        ArrayList<Integer> list = GetLeastNumbers_Solution(arr, 4);
        System.out.println(123);
    }
}